'''
AVL: 静态空间实现
'''
MAX = 10 ** 7 + 1

class AVL:
    def __init__(self):
        self.key = [0] * MAX
        self.value = [0] * MAX
        self.left = [0] * MAX
        self.right = [0] * MAX
        self.height = [0] * MAX
        self.id = 0
        self.root = 0
        self.size = 0

    def _up(self, root):  # 修正信息
        self.height[root] = 1 + max(self.height[self.left[root]], self.height[self.right[root]])

    def _left_rotate(self, root):  # 左旋,左边节点为新头，同时保证仍为搜索树
        right = self.right[root]
        self.right[root] = self.left[right]
        self.left[right] = root
        self._up(root)
        self._up(right)
        return right

    def _right_rotate(self, root):
        left = self.left[root]
        self.left[root] = self.right[left]
        self.right[left] = root
        self._up(root)
        self._up(left)
        return left

    def _maintain(self, root):
        if not root: return 0
        lh, rh = self.height[self.left[root]], self.height[self.right[root]]
        if lh - rh > 1:
            llh = self.height[self.left[self.left[root]]]
            lrh = self.height[self.right[self.left[root]]]
            if llh >= lrh:
                return self._right_rotate(root)
            else:
                self.left[root] = self._left_rotate(self.left[root])
                return self._right_rotate(root)
        elif rh - lh > 1:
            rrh = self.height[self.right[self.right[root]]]
            rlh = self.height[self.left[self.right[root]]]
            if rrh >= rlh:
                return self._left_rotate(root)
            else:
                self.right[root] = self._right_rotate(self.right[root])
                return self._left_rotate(root)
        return root  # 不违规，无需调整

    def _get(self, root, k):
        if not root:
            return 0
        elif k < self.key[root]:
            return self._get(self.left[root], k)
        elif k > self.key[root]:
            return self._get(self.right[root], k)
        return root

    def _add(self, root, k, v):
        if not root:
            self.id += 1
            self.key[self.id] = k
            self.value[self.id] = v
            self.height[self.id] = 1
            self.size += 1
            return self.id
        elif k < self.key[root]:
            self.left[root] = self._add(self.left[root], k, v)
        elif k > self.key[root]:
            self.right[root] = self._add(self.right[root], k, v)
        else:
            self.value[root] = v
        self._up(root)
        return self._maintain(root)

    def _delete(self, root, k):
        if not root:
            return 0
        elif k < self.key[root]:
            self.left[root] = self._delete(self.left[root], k)
        elif k > self.key[root]:
            self.right[root] = self._delete(self.right[root], k)
        else:
            # 没左没右直接删，只有一个孩子节点，孩子节点替换我
            if not self.left[root] and not self.right[root]:
                root = 0
            elif self.left[root] and not self.right[root]:
                root = self.left[root]
            elif self.right[root] and not self.left[root]:
                root = self.right[root]
            else:
                # 既有左又有右，选择右节点的最左节点替换我
                # 先删除它，同时保持平衡维护信息啥的，然后将它替换我
                most_left = self.right[root]  # 右树的最左节点
                while self.left[most_left]:
                    most_left = self.left[most_left]
                self.right[root] = self._delete_most_left(self.right[root], most_left)
                self.left[most_left] = self.left[root]
                self.right[most_left] = self.right[root]
                root = most_left
            self.size -= 1
        if root:
            self._up(root)
        return self._maintain(root)

    def _delete_most_left(self, root, most_left):
        if root == most_left: return self.right[most_left]
        self.left[root] = self._delete_most_left(self.left[root], most_left)
        self._up(root)
        return self._maintain(root)

    # ******************** 基本api ****************************
    def put(self, key, value):
        self.root = self._add(self.root, key, value)

    def get(self, key):
        target = self._get(self.root, key)
        if not target: return -1
        return self.value[target]

    def remove(self, key):
        self.root = self._delete(self.root, key)

    def __getitem__(self, key):
        target = self._get(self.root, key)
        if not target: raise KeyError(key)
        return self.value[target]

    def get_size(self):
        return self.size

    __setitem__ = put
    __delitem__ = remove
    __len__ = get_size

    def floor(self, key):
        def f(root):
            if not root: return float('-inf')
            if key < self.key[root]:
                return f(self.left[root])
            elif key > self.key[root]:
                return max(self.key[root], f(self.right[root]))
            else:
                return self.key[root]

        return f(self.root)

    def ceil(self, key):
        def f(root):
            if not root: return float('inf')
            if key < self.key[root]:
                return min(self.key[root], f(self.left[root]))
            elif key > self.key[root]:
                return f(self.right[root])
            else:
                return self.key[root]

        return f(self.root)



